package model.arbolBSharp;

import java.io.IOException;
import model.registro.RegistroFTRS;
import model.registro.RegistroHoja;



public class ArbolBSharp {

	private final int sizeNodo;

	/**
	 * La altura del arbol. Si es 0 significa que el arbol solo tiene un nodo
	 * hoja, que es la raiz.
	 */
	private int altura;
	private ManipuladorNodos buffer;

	/*
	 * Define el tamaó de los bloques de nodo 
	 */
	public ArbolBSharp(int sizeNodo) {
		this.sizeNodo = sizeNodo;
	}
	

	/*
	 * Define el archivo donde esta el arbol a utilizar
	 */
	public void abrir(String archivo) throws ArbolBSharpException {
		try {
			this.buffer = new ManipuladorNodos(new model.archivo.ArchivoBloques(archivo,
					sizeNodo));
		} catch (IOException e) {
			throw new ArbolBSharpException("Error al abrir el archivo en bloques", e);
		}

		if (this.buffer.getCatidadNodos() <= 2) {
			this.altura = 0;
		} else {
			try {
				Nodo nodoRaiz = buffer.leerNodoRaiz(0);
				this.altura = nodoRaiz.getNivel();
			} catch (ArbolBSharpException e) {
				throw new ArbolBSharpException("Error al leer el nodo raiz", e);
			}
		}
	}

	
	public void cerrar() throws ArbolBSharpException {
		this.buffer.flush();
		this.buffer.cerrar();
		this.buffer = null;
	}
	

	/*
	 * Esta funcion tiene toda la inteligencia necesaria para insertar un nuevo registro
	 * en el arbol manejando todas las excepciones que pueden haber en el arbol generadas 
	 * un desborde
	 * Recibe la palabra a agregar, su offset en el archivo de documentos y su peso global
	 */
	public void insertar(String palabra, int offset, float pesoGlobal) throws ArbolBSharpException {
		if (buffer == null)
			throw new ArbolBSharpException("No esta abierto el arbol");
	
			
		if (altura == 0) {
			insertarEnRaizHoja(palabra, offset, pesoGlobal);
		} else {
			Nodo[] nodos = new Nodo[altura];
			int siguientePuntero = buscarNodo(palabra, nodos,0);			
			Hoja hoja = buffer.leerHoja(siguientePuntero);

			/* verificar se se ha agregado una nueva clave mas grande al arbol */
			String claveMayorPrevia = null;
			boolean nuevaClaveMayor = false;
			if(palabra.compareTo(hoja.getPalabra((RegistroHoja)hoja.getMayorRegistro().clone())) > 0){
				nuevaClaveMayor = true;
				claveMayorPrevia = hoja.getPalabra((RegistroHoja)hoja.getMayorRegistro().clone());
			}
			
			/* Agregar la palabra en la hoja*/
			hoja.insertar(palabra, offset, pesoGlobal);
			
			/* Actualizar la clave mayor del arbol */
			if(nuevaClaveMayor){
				for (int i = 0; i < altura; i++) {
					nodos[i].reemplazarClave(claveMayorPrevia, palabra);
				}				
			}
			
			boolean ocurrioOverflow = false;
			if (!buffer.guardar(hoja)) {
				// tratar el  Overflow
				Nodo nodoPadre = nodos[altura - 1];
				if (!balancearHoja(hoja,nodoPadre)){
					this.dividirHoja(nodoPadre, hoja);
					ocurrioOverflow = true;
				}
			}
			
			//Manejar el overflow en cada nodo que estuvo en el camino que dio a la hoja
			int i = altura;
			while((ocurrioOverflow || nuevaClaveMayor) && i>0){
				i--;	
				if (i==0){
					if (!buffer.guardarRaiz(nodos[0])){
						if(!buffer.guardarRaiz(this.dividirRaiz(nodos[0])))
							throw new ArbolBSharpException("No se pudo guardar la nueva raiz");
						altura++;	
					} else ocurrioOverflow = true;
				}else{
					//if (!this.balancearNodo(nodos[i], nodos[i-1])){
						if(!buffer.guardar(nodos[i])){
							this.dividirNodo(nodos[i-1], nodos[i]);
							ocurrioOverflow = true;
						}	
					//}
					
				}
			}
		}
	}
	//
	//Busca la hoja o nodo de nivel especificado por el parametro nivel
	//que contiene dicha clave y devuelve el puntero desde el nodo anterior
	//Tambien devuelve un array con los nodos que pasaron en el recorrido
	//
	private int buscarNodo(String clave, Nodo[] nodos, int nivel) throws ArbolBSharpException {
		int siguientePuntero = 0;
		if (nivel == 0){
			for (int i = 0; i < altura; i++) {
				if (siguientePuntero == 0){
					nodos[i] = buffer.leerNodoRaiz(siguientePuntero);
					siguientePuntero = nodos[i].buscarPuntero(clave);
				}else{
					nodos[i] = buffer.leerNodo(siguientePuntero);
					siguientePuntero = nodos[i].buscarPuntero(clave);	
				}
			}
			return siguientePuntero;
		} else {
			for (int i = 0; i < (altura-nivel); i++) {
				if (siguientePuntero == 0){
					nodos[i] = buffer.leerNodoRaiz(siguientePuntero);
					siguientePuntero = nodos[i].buscarPuntero(clave);
				}else{
					nodos[i] = buffer.leerNodo(siguientePuntero);
					siguientePuntero = nodos[i].buscarPuntero(clave);	
				}
			}
			return siguientePuntero;
		}
	}
	
	/*
	 *Balancea la hoja en la que se produjo OVERFLOW y si no puede hacerlo
	 *devuelve false revirtiendo todas las modificaciones 
	 */
	private boolean balancearHoja(Hoja hoja, Nodo padre) throws ArbolBSharpException{
		//flag para registrar balanceo satisfactorio
		boolean balanceado = false;
		//verifico que la hoja tiene hermano derecho para balancear
		Integer punteroAHoja = padre.getPunteroAMayor();
		if (!punteroAHoja.equals(hoja.getPosicionEnArchivo())){
			//obtiene el registro que se debe deaplazar
			RegistroHoja regExtremoDer = hoja.getMayorRegistro();
			//Obtiene hermano derecho
			Integer punteroHnoDer = hoja.getPunteroASiguiente();
			Hoja hojaHnoDer = buffer.leerHoja(punteroHnoDer);
			
			//Obtiene la clave que se debe modificar en los nodos, la que se utilizara en el balanceo 
			String claveMayorPrevia = hoja.getPalabra(regExtremoDer);
			String claveBalanceo = hoja.getPalabra(regExtremoDer);
			
			hojaHnoDer.insertar(claveBalanceo, regExtremoDer.getOffset(), regExtremoDer.getPesoGlobal());

			if (buffer.guardar(hojaHnoDer)){
				// si pudo guardar el hermano derecho con su nuevo registro
				//remueve el registro de hoja para ver si puede esta guardarse sin el
				hoja.removerRegistro(regExtremoDer);
				if (buffer.guardar(hoja)){
					//se pudo balancear
					balanceado = true;
					// variables utilizadas para busqueda de nodo hoja
					Nodo[] nodos = new Nodo[altura];			
					//obtengo la nueva clave para reemplazar en los nodos
					String nuevaClave = hoja.getPalabra((RegistroHoja)hoja.getMayorRegistro().clone());
					buscarNodo(claveBalanceo, nodos,0);
					for (int i = 0; i < altura; i++) {
						if (i==0){
							//Es el padre
							nodos[altura-1].reemplazarClave(claveMayorPrevia, nuevaClave);
						}else{ 
							//verifico si la clave esta
							if((nodos[altura-i].esClaveMaxima(claveMayorPrevia))){
								nodos[altura-1-i].reemplazarClave(claveMayorPrevia, nuevaClave);
							}
						}
						if (i==altura-1){
							if (!buffer.guardarRaiz(nodos[0])){
								if(!buffer.guardarRaiz(this.dividirRaiz(nodos[0]))){
									throw new ArbolBSharpException("No se puede modificar raiz");
								}
							}	
						} else {
							if (!buffer.guardar(nodos[altura-1-i])){
								this.dividirNodo(nodos[altura-2-i], nodos[altura-1-i]);
							}
						}
					}
				} else {
					//Si no lo pudo guardar vuelve todo atras
					//remueve el registro que guardo en hermano
					//y lo vuelve a colocar en hoja
					hoja.insertar(claveBalanceo, regExtremoDer.getOffset(), regExtremoDer.getPesoGlobal());
					RegistroHoja regARemover = hojaHnoDer.getMenorRegistro();
					hojaHnoDer.removerRegistro(regARemover);
					
					if (!buffer.guardar(hojaHnoDer))
						throw new ArbolBSharpException("Error al guardar. La hoja no es la misma.");
				}
				
			} 
		
		}
		return balanceado;
	}

	/*
	 *Balancea los nodos en la que se produjo OVERFLOW y si no puede hacerlo
	 *devuelve false revirtiendo todas las modificaciones 
	 */
	private boolean balancearNodo(Nodo nodo, Nodo padre) throws ArbolBSharpException{
		boolean balanceado = false;
		Integer punteroANodo = padre.getPunteroAMayor();
		//Me fijo si no es el nodo del extremo derecho
		if (!punteroANodo.equals(nodo.getPosicionEnArchivo())){
			String claveBalanceo = nodo.getMayorClave();
			Integer punteroDeClave = nodo.getPunteroAMayor();
			
			Integer punteroAHnoDer = padre.getVecinoDerecho(nodo.getPosicionEnArchivo());
			Nodo nodoHnoDer = buffer.leerNodo(punteroAHnoDer);
			
			nodoHnoDer.agregarPrimero(claveBalanceo, punteroDeClave);
			if (buffer.guardar(nodoHnoDer)){
				nodo.removerClave(claveBalanceo);
				if (buffer.guardar(nodo)){
					balanceado = true;		
					Nodo[] nodos = new Nodo[altura-nodo.getNivel()];			
					//busca la el puntero a hoja y el recorrido para ubicarla
					//
					//Balanceo de nodos
					//
					String nuevaClave = nodo.getMayorClave();
					buscarNodo(claveBalanceo, nodos,nodo.getNivel());
					for (int i = 0; i < altura-nodo.getNivel(); i++) {
						if (i==0){
							nodos[altura-1-nodo.getNivel()].reemplazarClave(claveBalanceo, nuevaClave);
						}else{ 
							if((nodos[altura-i-nodo.getNivel()].esClaveMaxima(claveBalanceo))){
								nodos[altura-1-i-nodo.getNivel()].reemplazarClave(claveBalanceo, nuevaClave);
							}
						}
						if (i==altura-1-nodo.getNivel()){
							if (!buffer.guardarRaiz(nodos[0])){
								if(!buffer.guardarRaiz(this.dividirRaiz(nodos[0]))){
									throw new ArbolBSharpException("No se puede modificar raiz");
								}
							}	
						} else {
							if (!buffer.guardar(nodos[altura-1-i-nodo.getNivel()])){
								this.dividirNodo(nodos[altura-2-i-nodo.getNivel()], nodos[altura-1-i-nodo.getNivel()]);
							}
						}
					}		
				}  else {
					nodo.agregarPrefijo(claveBalanceo, punteroDeClave);
					nodoHnoDer.removerClave(claveBalanceo);
					buffer.guardar(nodoHnoDer);
				}
			}
		}
		return balanceado;
	}

	/*
	 * Divide el nodo que se pasa por parametro con su hermano derecho creando un nodo mas
	 * y dividiendo el contenido entre tres nodos. En el padre se modifican las claves.
	 */
	private void dividirNodo(Nodo nodoPadre, Nodo nodo) throws ArbolBSharpException {			
		String aux = nodo.getMayorClave();
		Nodo  nodoDer = null;
		//No tiene hermano derecho
		if (nodoPadre.esClaveMaxima(aux)){
			nodoDer = nodo;
			Integer punteroHno = nodoPadre.getVecinoIzquierdo(nodo.getPosicionEnArchivo()); 
			nodo = buffer.leerNodo(punteroHno);
		} else {
			Integer punteroHno = nodoPadre.getVecinoDerecho(nodo.getPosicionEnArchivo()); 
			nodoDer = buffer.leerNodo(punteroHno);
			
		}
		// Dividir
		String claveNodo = nodo.getMayorClave();
		String claveNodoDer = nodoDer.getMayorClave();

		
		Nodo nuevoNodoDer = new Nodo();
		nodo.dividirNodo(nodoDer,nuevoNodoDer);

		nuevoNodoDer.setPosicionEnArchivo(buffer.getBloqueLibre());
		nuevoNodoDer.setNivel(nodo.getNivel());
			
		if (!buffer.guardar(nodo) ||
			!buffer.guardar(nodoDer)||
			!buffer.guardar(nuevoNodoDer))
				throw new ArbolBSharpException("No se pueden guardar los nodos");
		
		nodoPadre.reemplazarClave(claveNodo, nodo.getMayorClave());
		nodoPadre.reemplazarClave(claveNodoDer, nodoDer.getMayorClave());
		nodoPadre.agregarPrefijo(nuevoNodoDer.getMayorClave(), nuevoNodoDer.getPosicionEnArchivo());		
	}

	/*
	 *Divide el nodo raiz en tres nodos y genera la nueva raiz con un nivel superior
	 *Aumenta la altura 
	 */
	private Nodo dividirRaiz(Nodo raiz) throws ArbolBSharpException {
	
		Nodo nodoCentral = new Nodo();
		Nodo nodoDerecho = new Nodo();
		
		nodoDerecho.setNivel(raiz.getNivel());
		nodoCentral.setNivel(raiz.getNivel());
		
		raiz.dividirNodo(nodoCentral,nodoDerecho);
		
		nodoDerecho.setPosicionEnArchivo(buffer.getBloqueLibre());
		if(!buffer.guardar(nodoDerecho))
			throw new ArbolBSharpException("No se puede guardar el nodo");
		
		nodoCentral.setPosicionEnArchivo(buffer.getBloqueLibre());
		if(!buffer.guardar(nodoCentral))
			throw new ArbolBSharpException("No se puede guardar el nodo");
		
		raiz.setPosicionEnArchivo(buffer.getBloqueLibre());
		if(!buffer.guardar(raiz))
			throw new ArbolBSharpException("No se puede guardar el nodo");
		
		Nodo nuevaRaiz = new Nodo();
		nuevaRaiz.setPosicionEnArchivo(0);
		nuevaRaiz.setNivel(altura + 1);
		
		nuevaRaiz.agregarPrefijo(nodoDerecho.getMayorClave(), nodoDerecho.getPosicionEnArchivo());
		nuevaRaiz.agregarPrefijo(raiz.getMayorClave(), raiz.getPosicionEnArchivo());
		
						
		return nuevaRaiz;
	}
	
	/*
	 * Divide la hoja que se pasa por parametro con su hermano derecho creando un nodo mas
	 * y dividiendo el contenido entre tres nodos. En el padre se modifican las claves.
	 */
	private void dividirHoja(Nodo nodoPadre, Hoja hoja) throws ArbolBSharpException {
		RegistroHoja regAux = (RegistroHoja)hoja.getMayorRegistro().clone();
		Hoja hojaDer = null;
		if (nodoPadre.esClaveMaxima(hoja.getPalabra(regAux))){
			hojaDer = hoja;
			Integer punteroHno = nodoPadre.getVecinoIzquierdo(hoja.getPosicionEnArchivo()); 
			hoja = buffer.leerHoja(punteroHno);
		} else {
			Integer punteroHno = nodoPadre.getVecinoDerecho(hoja.getPosicionEnArchivo()); 
			hojaDer = buffer.leerHoja(punteroHno);
			
		}
		String claveNodoI = hoja.getPalabra((RegistroHoja)hoja.getMayorRegistro().clone());
		String claveNodoD = hojaDer.getPalabra((RegistroHoja)hojaDer.getMayorRegistro().clone());
		Hoja nuevaHojaI = new Hoja();
		Hoja nuevaHojaD = new Hoja();
		nuevaHojaD.setPosicionEnArchivo(buffer.getBloqueLibre());
		hoja.dividirHoja(nuevaHojaI,hojaDer,nuevaHojaD);
		
		if (!buffer.guardar(nuevaHojaI) ||
			!buffer.guardar(nuevaHojaD)||
			!buffer.guardar(hojaDer))
			throw new ArbolBSharpException("Error al guardar los nodos divididos"); 
		
		// Actualizar el nodo padre			
		nodoPadre.reemplazarClave(claveNodoI, nuevaHojaI.getPalabra((RegistroHoja)nuevaHojaI.getMayorRegistro().clone()));
		nodoPadre.reemplazarClave(claveNodoD, hojaDer.getPalabra((RegistroHoja)hojaDer.getMayorRegistro().clone()));
		nodoPadre.agregarPrefijo(nuevaHojaD.getPalabra(nuevaHojaD.getMayorRegistro()), nuevaHojaD.getPosicionEnArchivo());
	}

	/*
	 *Inserta ña clave en la raiz cuando esta es hoja 
	 */
	private void insertarEnRaizHoja(String palabra, int offset, float tamanioGlobal) throws ArbolBSharpException {
		Hoja raiz;
		if (buffer.getCatidadNodos() == 0) {
			//el archivo esta vacio
			raiz = new Hoja();
			raiz.setPosicionEnArchivo(0);
		} else {
			raiz = buffer.leerHojaRaiz(0);
		}
		raiz.insertar(palabra, offset, tamanioGlobal);
		
		if (!buffer.guardarRaiz(raiz)) {
		// 	OVERFLOW
			//System.out.println("\n\nDivision de Raiz hoja\n\n");
			Hoja nodoIzquierda = new Hoja();
			Hoja nodoCentral = new Hoja();
			Hoja nodoDerecha = new Hoja();
			Nodo nuevaRaiz = new Nodo();
			nodoCentral.setPosicionEnArchivo(2);
			nodoCentral.setPunteroASiguiente(2);
			
			raiz.dividirHoja(nodoIzquierda,nodoCentral,nodoDerecha);
			
			nodoDerecha.setPosicionEnArchivo(buffer.getBloqueLibre());
			nodoDerecha.setPunteroASiguiente(0);
			if (!buffer.guardar(nodoDerecha))
				throw new ArbolBSharpException("Error: no se puede dividir el nodo raiz hoja");			
			nodoCentral.setPunteroASiguiente(nodoDerecha.getPosicionEnArchivo());
			nodoCentral.setPosicionEnArchivo(buffer.getBloqueLibre());
			if (!buffer.guardar(nodoCentral))
				throw new ArbolBSharpException("Error: no se puede dividir el nodo");
			
			nodoIzquierda.setPunteroASiguiente(nodoCentral.getPosicionEnArchivo());
			nodoIzquierda.setPosicionEnArchivo(buffer.getBloqueLibre());
			if (!buffer.guardar(nodoIzquierda))
				throw new ArbolBSharpException("Error: no se puede dividir el nodo");
			
			nuevaRaiz.agregarPrimero(nodoDerecha.getPalabra((RegistroHoja)nodoDerecha.getMayorRegistro().clone()), nodoDerecha.getPosicionEnArchivo());
			nuevaRaiz.agregarPrimero(nodoCentral.getPalabra((RegistroHoja)nodoCentral.getMayorRegistro().clone()), nodoCentral.getPosicionEnArchivo());
			nuevaRaiz.agregarPrimero(nodoIzquierda.getPalabra((RegistroHoja)nodoIzquierda.getMayorRegistro().clone()), nodoIzquierda.getPosicionEnArchivo());
			nuevaRaiz.setPosicionEnArchivo(0);
			nuevaRaiz.setNivel(1);

			if (!buffer.guardarRaiz(nuevaRaiz))
				throw new ArbolBSharpException("Error: no se puede dividir el nodo");
			altura++;
		}
	}
	
	/*
	 *Verifica si el arbol que se creo esta vacio 
	 */
	public boolean isEmpty() throws ArbolBSharpException {
		if ((int)buffer.getCatidadNodos()==0)
			return true;
		else
			return false;
	}

	/*
	 * Recibe una palabra y devuelve un registro con la palabra su offset y su peso global 
	 */
	public RegistroFTRS buscarPalabra(String palabra) throws ArbolBSharpException{
		Integer punteroHoja = this.buscarNodo(palabra, new Nodo[altura], 0);
		Hoja hoja = buffer.leerHoja(punteroHoja);
		RegistroFTRS registro = new RegistroFTRS();
		RegistroHoja regHoja = hoja.buscarRegistro(palabra);
		if (regHoja == null){
			return null;
		}
		regHoja = (RegistroHoja)regHoja.clone();
		registro.setPalabra(hoja.getPalabra(regHoja));
		registro.setOffSetDocumentos(regHoja.getOffset());
		registro.setPesoGlobal(regHoja.getPesoGlobal());
		return registro;
		
	}


}
